In the area of computer graphics and video processing, there is a constant effort to improve the rendering capabilities of such systems to achieve more realistic images with less computational effort.
Traditionally, texture mapping onto projections of 3D surfaces have been performed by inverse mapping from an area of the pixel onto surface texture. An alternative approach is shown in “3-d transformations of images in scanline order” by Edwin Catmull and Alvy Ray Smith, In Computer Graphics (SIGGRAPH '80 Proceedings), volume 14(3), pages 279-285, 1980. The texture surface is transformed as a 2D image until it conforms to a projection of a polygon placed arbitrarily in 3D space. This 2D transformation or mapping can be decomposed into a sequence of two orthogonal 1D transformations, namely in a horizontal and in a vertical scanline order. In other words, multi-dimensional image transformations of resampling operations can be executed as a sequence of one dimensional transformation.
However, one problem, that may arise within such a sequence of 1D transformations, is the occurrence of aliasing due to shear. The shear problem is illustrated in FIG. 1 showing two lines of a texture map (left side of FIG. 1) and an intermediate image (right side of FIG. 1). The texture map has a black vertical line (at u=1), and the shear due to the perspective mapping is uttered such that the black pixel in the second line is shifted five pixels more to the right (x=6) than the black pixel on the first line (x=1). In order to prevent such horizontal aliasing, a horizontal filter pass is performed, which however can not prevent vertical aliasing. The shear causes a very sharp transition between black pixels in one line, and white pixels in the next. Also, the line in the intermediate image consists of disjunctive parts, separated by columns to which the line does not contribute (e.g. for x=3).
One solution to the shear problem is the so-called super-sampling technique proposed by George Wolberg and Terrance E. Boult in “Separable image warping with spatial lookup tables”, in Computer Graphics (Proc. Siggraph '89), volume 23(3), pages 369-378, July 1989. Accordingly, the problem of aliasing occurs due to an under-sampling, so that a suggested solution is to increase the resolution by sampling the mapping function more densely. Therefore, the rasterisation is performed at a finer resolution (i.e. it is super-sampled), causing extra intermediate lines to be generated, with a black pixel at intermediate positions filling the holes. If this is done for shear introduced by a first pass, the second pass will down-scale the larger intermediate image to its final resolution. If shear in the second pass would be treated using the same supersampling approach, a third pass would be needed to reduce the generated higher horizontal resolution to the output resolution. Accordingly, the super-sampling technique is a compute intensive approach.
Another approach to overcome the aliasing problem is based on a box filtering technique as described by Alvy Ray Smith, in “Planar 2-pass texture mapping and warping”, in Computer Graphics (Proceedings Siggraph 1987), volume 21(4), pages 263-272, 1987. Here, prefiltering is applied and constitutes a process of checking whether a pixel is inside e.g. a triangle (for the case of inverse mapping). The prefilter may have a delta function, a box function or the like. Without prefiltering each texel in the input texture is either mapped to screen space or not depending whether its position lies within the triangle. A prefilter is used to determine which texels should contribute to a subsequent resampling, i.e. also possibly those not totally inside the triangle, in order to reduce edge aliasing. An amount of overlap is determined between the triangle and a footprint of the prefilter, wherein the footprint of a prefilter corresponds to the area of the prefilter in the u/v directions in texture space.
FIG. 2 shows an illustration of an output pixel footprint mapped to the input image. The left side of FIG. 2 shows a texture map 76, i.e. texels, in texture space, while the right side of FIG. 2 shows an intermediate image after horizontal transformation 77, i.e. pixels. The texture comprises a vertical column of grey texels 74. In the texture space, the square 72 depicts a box reconstructed footprint of a texel, ML the midline, 75 white texels and 73 a mapped box reconstructed prefilter footprint of a pixel. A box prefilter footprint of a pixel on a scanline 78 is shown in screen space. Accordingly, the footprint 78 of a box prefilter of the pixel on a scanline, indicated by the midline ML, is mapped to the texture space 76 and constitutes the mapped box reconstruction prefilter footprint.
In FIG. 2 a horizontal span of output pixels are modeled as a row of neighboring squares representing footprints of a box prefilter. The footprint 73 of these pixels mapped to the scanline of the input image constitutes an area limited above and below by parallel line segments and left and right by curves and in particular straight lines for some transformations as shown in FIG. 2.
The pixel color being box filtered is composed of the average of the texel colors whose footprints of the box reconstruction filter intersects the mapped footprint 73 of the pixel. A weighting function is performed on the texels in accordance of the size of the footprint area of the reconstruction filter 72 intersecting with the pixel's mapped footprint 73, i.e. in accordance with the area overlap of the footprint area of the reconstruction filter and the footprint of the mapped pixel. Although, a more accurate average can thus be achieved than a strictly 1D average over the midline ML of these areas (selecting only the dark texel to contribute in FIG. 2), 2D computations (i.e. area overlap calculation) are required within the 1D scanline computations, resulting in a compute intensive technique.